package org.example.day;

import java.util.Arrays;

/**
 * @Description: TODO
 * @Author wyatt
 * @Data 2024/07/02 15:40
 */
//给你一个整数数组 nums。
//
// 返回两个（不一定不同的）质数在 nums 中 下标 的 最大距离。
//
//
//
// 示例 1：
//
//
// 输入： nums = [4,2,9,5,3]
//
//
// 输出： 3
//
// 解释： nums[1]、nums[3] 和 nums[4] 是质数。因此答案是 |4 - 1| = 3。
//
// 示例 2：
//
//
// 输入： nums = [4,8,2,8]
//
//
// 输出： 0
//
// 解释： nums[2] 是质数。因为只有一个质数，所以答案是 |2 - 2| = 0。
//
//
//
// 提示：
//
//
// 1 <= nums.length <= 3 * 10⁵
// 1 <= nums[i] <= 100
// 输入保证 nums 中至少有一个质数。
//
//
// Related Topics 数组 数学 数论 👍 20 👎 0

public class Solution3115 {

    public static void main(String[] args) {
        System.out.println(new Solution3115().maximumPrimeDifference(new int[]{4,2,9,5,3}));
    }

    public int maximumPrimeDifference(int[] nums) {
        boolean[] isPrime = new boolean[101];
        Arrays.fill(isPrime, true);
        isPrime[0] = false;
        isPrime[1] = false;
        for(int i=2;i<=10;i++){
            for(int j=i; i*j<=100;j++){
                isPrime[i*j] = false;
            }
        }

        int start = nums.length;
        int end = 0;

        for (int i = 0; i < nums.length; i++) {
            if(isPrime[nums[i]]){
                start = Math.min(start, i);
                end = Math.max(end, i);
            }
        }

        return end >= start ? end - start : 0;
    }
}
